home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / source.exe / POSIX / BSDPSX / FTS.C < prev    next >
C/C++ Source or Header  |  1992-09-17  |  24KB  |  866 lines
  1.  /* Copyright (c) 1990 The Regents of the University of California.
  2.  * All rights reserved.
  3.  *
  4.  * Redistribution and use in source and binary forms, with or without
  5.  * modification, are permitted provided that the following conditions
  6.  * are met:
  7.  * 1. Redistributions of source code must retain the above copyright
  8.  *    notice, this list of conditions and the following disclaimer.
  9.  * 2. Redistributions in binary form must reproduce the above copyright
  10.  *    notice, this list of conditions and the following disclaimer in the
  11.  *    documentation and/or other materials provided with the distribution.
  12.  * 3. All advertising materials mentioning features or use of this software
  13.  *    must display the following acknowledgement:
  14.  *    This product includes software developed by the University of
  15.  *    California, Berkeley and its contributors.
  16.  * 4. Neither the name of the University nor the names of its contributors
  17.  *    may be used to endorse or promote products derived from this software
  18.  *    without specific prior written permission.
  19.  *
  20.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30.  * SUCH DAMAGE.
  31.  */
  32.  
  33. #ifdef DF_POSIX
  34. #include <misc.h>
  35. #endif
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)fts.c    5.19 (Berkeley) 5/9/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/cdefs.h>
  42. #ifdef _POSIX_SOURCE         //DF_DSC POSIX does not need this
  43. #else                       //      only MAXPATHLEN was found there
  44.     #include <sys/param.h>  //      and it wants machine directory stuff
  45. #endif
  46. #include <sys/stat.h>
  47. #include <fcntl.h>
  48. #include <dirent.h>
  49. #include <errno.h>
  50. #include "fts.h"
  51. #include <stdlib.h>
  52. #include <string.h>
  53. #include <unistd.h>
  54.  
  55. static FTSENT *fts_alloc(), *fts_build(), *fts_sort();
  56. static void fts_load(), fts_lfree();
  57. static u_short fts_stat();
  58. static char *fts_path();
  59.  
  60. #define    ISSET(opt)    (sp->fts_options & opt)
  61. #define    SET(opt)    (sp->fts_options |= opt)
  62.  
  63. #define    CHDIR(sp, path)    (!ISSET(FTS_NOCHDIR) && chdir(path))
  64.  
  65. #ifdef _POSIX_SOURCE        //DF_DSC fchdir not in POSIX
  66. #else
  67. #define    FCHDIR(sp, fd)    (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  68. #endif
  69.  
  70. /* fts_build flags */
  71. #define    BCHILD        1        /* from fts_children */
  72. #define    BREAD        2        /* from fts_read */
  73.  
  74. FTS *
  75. fts_open(argv, options, compar)
  76.     char * const *argv;
  77.     register int options;
  78.     int (*compar)();
  79. {
  80.     register FTS *sp;
  81.     register FTSENT *p, *root;
  82.     register int nitems, maxlen;
  83.     FTSENT *parent, *tmp;
  84.     int len;
  85.  
  86.     /* Allocate/initialize the stream */
  87.     if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))
  88.         return(NULL);
  89.     bzero(sp, sizeof(FTS));
  90.     sp->fts_compar = compar;
  91.     sp->fts_options = options;
  92.  
  93.     /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
  94.     if (ISSET(FTS_LOGICAL))
  95.         SET(FTS_NOCHDIR);
  96.  
  97. // force NOCHDIR because chdir("..") fails for large trees  //DF_DSC
  98.     SET(FTS_NOCHDIR);
  99.  
  100.  
  101.     /* Allocate/initialize root's parent. */
  102.     if (!(parent = fts_alloc(sp, "", 0)))
  103.         goto mem1;
  104.     parent->fts_level = FTS_ROOTPARENTLEVEL;
  105.  
  106.     /* Allocate/initialize root(s). */
  107.     maxlen = -1;
  108.     for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
  109.         if (!(len = strlen(*argv))) {
  110.             errno = ENOENT;
  111.             goto mem2;
  112.         }
  113.         if (maxlen < len)
  114.             maxlen = len;
  115.         p = fts_alloc(sp, *argv, len);
  116.         p->fts_level = FTS_ROOTLEVEL;
  117.         p->fts_parent = parent;
  118.         /*
  119.          * If comparison routine supplied, traverse in sorted
  120.          * order; otherwise traverse in the order specified.
  121.          */
  122.         if (compar) {
  123.             p->fts_link = root;
  124.             root = p;
  125.             p->fts_accpath = p->fts_name;
  126.             if (!(options & FTS_NOSTAT))
  127.                 p->fts_info = fts_stat(sp, p, 0);
  128.         } else {
  129.             p->fts_link = NULL;
  130.             if (!root)
  131.                 tmp = root = p;
  132.             else {
  133.                 tmp->fts_link = p;
  134.                 tmp = p;
  135.             }
  136.         }
  137.     }
  138.     if (compar && nitems > 1)
  139.         root = fts_sort(sp, root, nitems);
  140.  
  141.     /*
  142.      * Allocate a dummy pointer and make fts_read think that we've just
  143.      * finished the node before the root(s); set p->fts_info to FTS_NS
  144.      * so that everything about the "current" node is ignored.
  145.      */
  146.     if (!(sp->fts_cur = fts_alloc(sp, "", 0)))
  147.         goto mem2;
  148.     sp->fts_cur->fts_link = root;
  149.     sp->fts_cur->fts_info = FTS_NS;
  150.  
  151.     /* Start out with at least 1K+ of path space. */
  152. #ifdef _POSIX_SOURCE        //DF_POSIX  POSIX defines PATH_MAX
  153.     if (!fts_path(sp, __max(maxlen, PATH_MAX)))
  154.             goto mem3;
  155.     if ((sp->fts_rpath = malloc(PATH_MAX)) == NULL)
  156.             goto mem4;
  157. #else
  158.     if (!fts_path(sp, MAX(maxlen, MAXPATHLEN)))
  159.         goto mem3;
  160. #endif
  161.  
  162.     /*
  163.      * If using chdir(2), grab a file descriptor pointing to dot to insure
  164.      * that we can get back here; this could be avoided for some paths,
  165.      * but almost certainly not worth the effort.  Slashes, symbolic links,
  166.      * and ".." are all fairly nasty problems.  Note, if we can't get the
  167.      * descriptor we run anyway, just more slowly.
  168.      */
  169. #ifdef _POSIX_SOURCE        //DF_DSC use getpwd because no fchdir for later
  170.     if (!ISSET(FTS_NOCHDIR) && (getcwd(sp->fts_rpath, PATH_MAX)) == NULL)
  171. #else
  172.     if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
  173. #endif
  174.         SET(FTS_NOCHDIR);
  175.  
  176.     return(sp);
  177. #ifdef _POSIX_SOURCE        //DF_DSC
  178. mem4:   free(sp->fts_path);
  179. #endif
  180. mem3:    free(sp->fts_cur);
  181. mem2:    fts_lfree(root);
  182.     free(parent);
  183. mem1:    free(sp);
  184.     return(NULL);
  185. }
  186.  
  187. static void
  188. fts_load(sp, p)
  189.     FTS *sp;
  190.     register FTSENT *p;
  191. {
  192.     register int len;
  193.     register char *cp;
  194.  
  195.     /*
  196.      * Load the stream structure for the next traversal.  Since we don't
  197.      * actually enter the directory until after the preorder visit, set
  198.      * the fts_accpath field specially so the chdir gets done to the right
  199.      * place and the user can access the first node.
  200.      */
  201.     len = p->fts_pathlen = p->fts_namelen;
  202.     bcopy(p->fts_name, sp->fts_path, len + 1);
  203.     if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
  204.         len = strlen(++cp);
  205.         bcopy(cp, p->fts_name, len + 1);
  206.         p->fts_namelen = len;
  207.     }
  208.     p->fts_accpath = p->fts_path = sp->fts_path;
  209.  
  210.     p->fts_info = fts_stat(sp, p, 0);
  211.     sp->rdev = p->fts_statb.st_dev;
  212. }
  213.  
  214. fts_close(sp)
  215.     FTS *sp;
  216. {
  217.     register FTSENT *freep, *p;
  218.     int saved_errno;
  219.  
  220.     if (sp->fts_cur) {
  221.         /*
  222.          * This still works if we haven't read anything -- the dummy
  223.          * structure points to the root list, so we step through to
  224.          * the end of the root list which has a valid parent pointer.
  225.          */
  226.         for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) {
  227.             freep = p;
  228.             p = p->fts_link ? p->fts_link : p->fts_parent;
  229.             free(freep);
  230.         }
  231.         free(p);
  232.     }
  233.  
  234.     /* Free up child linked list, sort array, path buffer. */
  235.     if (sp->fts_child)
  236.         fts_lfree(sp->fts_child);
  237.     if (sp->fts_array)
  238.         free(sp->fts_array);
  239.     free(sp->fts_path);
  240.  
  241.     /* Return to original directory, save errno if necessary. */
  242.     if (!ISSET(FTS_NOCHDIR)) {
  243. #ifdef _POSIX_SOURCE
  244.         saved_errno = chdir(sp->fts_rpath) ? errno : 0;
  245.                 free(sp->fts_rpath);
  246. #else
  247.         saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
  248.         (void)close(sp->fts_rfd);
  249. #endif
  250.     }
  251.  
  252.     /* Free up the stream pointer. */
  253.     free(sp);
  254.  
  255.     /* Set errno and return. */
  256.     if (!ISSET(FTS_NOCHDIR) && saved_errno) {
  257.         errno = saved_errno;
  258.         return(-1);
  259.     }
  260.     return(0);
  261. }
  262.  
  263. /*
  264.  * Special case a root of "/" so that slashes aren't appended causing
  265.  * paths to be written as "//foo".
  266.  */
  267. #define    NAPPEND(p) \
  268.     (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
  269.         p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
  270.  
  271. FTSENT *
  272. fts_read(sp)
  273.     register FTS *sp;
  274. {
  275.     register FTSENT *p, *tmp;
  276.     register int instr;
  277.     register char *t;
  278.  
  279.     /* If finished or unrecoverable error, return NULL. */
  280.     if (!sp->fts_cur || ISSET(FTS_STOP))
  281.         return(NULL);
  282.  
  283.     /* Set current node pointer. */
  284.     p = sp->fts_cur;
  285.  
  286.     /* Save and zero out user instructions. */
  287.     instr = p->fts_instr;
  288.     p->fts_instr = FTS_NOINSTR;
  289.  
  290.     /* If used fts_link pointer for cycle detection, restore it. */
  291.     if (sp->fts_savelink) {
  292.         p->fts_link = sp->fts_savelink;
  293.         sp->fts_savelink = NULL;
  294.     }
  295.  
  296.     /* Any type of file may be re-visited; re-stat and re-turn. */
  297.     if (instr == FTS_AGAIN) {
  298.         p->fts_info = fts_stat(sp, p, 0);
  299.         return(p);
  300.     }
  301.  
  302.     /*
  303.      * Following a symlink -- SLNONE test allows application to see
  304.      * SLNONE and recover.
  305.      */
  306.     if (instr == FTS_FOLLOW &&
  307.         (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
  308.         p->fts_info = fts_stat(sp, p, 1);
  309.         return(p);
  310.     }
  311.  
  312.     /* Directory in pre-order. */
  313.     if (p->fts_info == FTS_D) {
  314.         /* If skipped or crossed mount point, do post-order visit. */
  315.         if (instr == FTS_SKIP ||
  316.             ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) {
  317.             if (sp->fts_child) {
  318.                 fts_lfree(sp->fts_child);
  319.                 sp->fts_child = NULL;
  320.             }
  321.             p->fts_info = FTS_DP;
  322.             return(p);
  323.         } 
  324.  
  325.         /*
  326.          * Cd to the subdirectory, reading it if haven't already.  If
  327.          * the read fails for any reason, or the directory is empty,
  328.          * the fts_info field of the current node is set by fts_build.
  329.          * If have already read and now fail to chdir, whack the list
  330.          * to make the names come out right, and set the parent state
  331.          * so the application will eventually get an error condition.
  332.          * If haven't read and fail to chdir, check to see if we're
  333.          * at the root node -- if so, we have to get back or the root
  334.          * node may be inaccessible.
  335.          */
  336.         if (sp->fts_child) {
  337.             if (CHDIR(sp, p->fts_accpath)) {
  338.                 p->fts_parent->fts_cderr = errno;
  339.                 for (p = sp->fts_child; p; p = p->fts_link)
  340.                     p->fts_accpath =
  341.                         p->fts_parent->fts_accpath;
  342.             }
  343.         } else if (!(sp->fts_child = fts_build(sp, BREAD))) {
  344.             if ISSET(FTS_STOP)
  345.                 return(NULL);
  346. #ifdef _POSIX_SOURCE
  347.             if (p->fts_level == FTS_ROOTLEVEL &&
  348.                 CHDIR (sp, sp->fts_rpath)) {
  349.                 SET(FTS_STOP);
  350.                 return(NULL);
  351.             }
  352. #else
  353.             if (p->fts_level == FTS_ROOTLEVEL &&
  354.                 FCHDIR(sp, sp->fts_rfd)) {
  355.                 SET(FTS_STOP);
  356.                 return(NULL);
  357.             }
  358. #endif
  359.             return(p);
  360.         }
  361.         p = sp->fts_child;
  362.         sp->fts_child = NULL;
  363.         goto name;
  364.     }
  365.  
  366.     /* Move to next node on this level. */
  367. next:    tmp = p;
  368.     if (p = p->fts_link) {
  369.         free(tmp);
  370.  
  371.         /* If reached the top, load the paths for the next root. */
  372.         if (p->fts_level == FTS_ROOTLEVEL) {
  373.             fts_load(sp, p);
  374.             return(sp->fts_cur = p);
  375.         }
  376.  
  377.         /* User may have called fts_set on the node. */
  378.         if (p->fts_instr == FTS_SKIP)
  379.             goto next;
  380.         if (p->fts_instr == FTS_FOLLOW) {
  381.             p->fts_info = fts_stat(sp, p, 1);
  382.             p->fts_instr = FTS_NOINSTR;
  383.         }
  384.  
  385. name:        t = sp->fts_path + NAPPEND(p->fts_parent);
  386.         *t++ = '/';
  387.         bcopy(p->fts_name, t, p->fts_namelen + 1);
  388.         return(sp->fts_cur = p);
  389.     }
  390.  
  391.     /* Move up to the parent node. */
  392.     p = tmp->fts_parent;
  393.     free(tmp);
  394.  
  395.     if (p->fts_level == FTS_ROOTPARENTLEVEL) {
  396.         /*
  397.          * Done; free everything up and set errno to 0 so the user
  398.          * can distinguish between error and EOF.
  399.          */
  400.         free(p);
  401.         errno = 0;
  402.         return(sp->fts_cur = NULL);
  403.     }
  404.  
  405.     sp->fts_path[p->fts_pathlen] = '\0';
  406.  
  407.     /*
  408.      * Cd back up to the parent directory.  If at a root node, have to cd
  409.      * back to the original place, otherwise may not be able to access the
  410.      * original node on post-order.
  411.      */
  412.     if (p->fts_level == FTS_ROOTLEVEL) {
  413. #ifdef _POSIX_SOURCE
  414.         if (CHDIR (sp, sp->fts_rpath)) {
  415. #else
  416.         if (FCHDIR(sp, sp->fts_rfd)) {
  417. #endif
  418.             SET(FTS_STOP);
  419.             return(NULL);
  420.         }
  421.     }
  422.     else if (CHDIR(sp, "..")) {
  423.         SET(FTS_STOP);
  424.         return(NULL);
  425.     }
  426.  
  427.     /* 
  428.      * If had a chdir error when trying to get into the directory, set the
  429.      * info field to reflect this, and restore errno.  The error indicator
  430.      * has to be reset to 0 so that if the user does an FTS_AGAIN, it all
  431.      * works.
  432.      */
  433.     if (p->fts_cderr) {
  434.         errno = p->fts_cderr;
  435.         p->fts_cderr = 0;
  436.         p->fts_info = FTS_ERR;
  437.     } else
  438.         p->fts_info = FTS_DP;
  439.     return(sp->fts_cur = p);
  440. }
  441.  
  442. /*
  443.  * Fts_set takes the stream as an argument although it's not used in this
  444.  * implementation; it would be necessary if anyone wanted to add global
  445.  * semantics to fts using fts_set.  An error return is allowed for similar
  446.  * reasons.
  447.  */
  448. /* ARGSUSED */
  449. fts_set(sp, p, instr)
  450.     FTS *sp;
  451.     FTSENT *p;
  452.     int instr;
  453. {
  454.     p->fts_instr = instr;
  455.     return(0);
  456. }
  457.  
  458. FTSENT *
  459. fts_children(sp)
  460.     register FTS *sp;
  461. {
  462.     register FTSENT *p;
  463.     int fd;
  464. #ifdef _POSIX_SOURCE            //DF_DSC
  465.         char this_path [PATH_MAX];
  466. #endif
  467.         
  468.     /* Set current node pointer. */
  469.     p = sp->fts_cur;
  470.  
  471.     /*
  472.      * Set errno to 0 so that user can tell the difference between an
  473.      * error and a directory without entries.  If not a directory being
  474.      * visited in *pre-order*, or we've already had fatal errors, return
  475.      * immediately.
  476.      */
  477.     errno = 0;
  478.     if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR)
  479.         return(NULL);
  480.  
  481.     /* Free up any previous child list. */
  482.     if (sp->fts_child)
  483.         fts_lfree(sp->fts_child);
  484.  
  485.     /*
  486.      * If using chdir on a relative path and called BEFORE fts_read does
  487.      * its chdir to the root of a traversal, we can lose -- we need to
  488.      * chdir into the subdirectory, and we don't know where the current
  489.      * directory is, so we can't get back so that the upcoming chdir by
  490.      * fts_read will work.
  491.      */
  492.     if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
  493.         ISSET(FTS_NOCHDIR))
  494.         return(sp->fts_child = fts_build(sp, BCHILD));
  495. #ifdef _POSIX_SOURCE     //DF_DSC  Because no fchdir
  496.         if ((getcwd(this_path, PATH_MAX)) == NULL)
  497. #else
  498.     if ((fd = open(".", O_RDONLY, 0)) < 0)
  499. #endif
  500.         return(NULL);
  501.     sp->fts_child = fts_build(sp, BCHILD);
  502. #ifdef _POSIX_SOURCE
  503.     if (chdir(this_path))
  504.         return(NULL);
  505. #else
  506.     if (fchdir(fd))
  507.         return(NULL);
  508.     (void)close(fd);
  509. #endif
  510.     return(sp->fts_child);
  511. }
  512.  
  513. /*
  514.  * This is the tricky part -- do not casually change *anything* in here.  The
  515.  * idea is to build the linked list of entries that are used by fts_children
  516.  * and fts_read.  There are lots of special cases.
  517.  *
  518.  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  519.  * set and it's a physical walk (so that symbolic links can't be directories),
  520.  * we assume that the number of subdirectories in a node is equal to the number
  521.  * of links to the parent.  This allows stat calls to be skipped in any leaf
  522.  * directories and for any nodes after the directories in the parent node have
  523.  * been found.  This empirically cuts the stat calls by about 2/3.
  524.  */
  525. #define    ISDOT(a)    (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
  526.  
  527. static FTSENT *
  528. fts_build(sp, type)
  529.     register FTS *sp;
  530.     int type;
  531. {
  532.     register struct dirent *dp;
  533.     register FTSENT *p, *head;
  534.     register int nitems;
  535.     FTSENT *cur;
  536.     DIR *dirp;
  537.     int cderr, descend, len, level, maxlen, nlinks, saved_errno;
  538.     char *cp;
  539.  
  540.     /* Set current node pointer. */
  541.     cur = sp->fts_cur;
  542.  
  543.     /*
  544.      * Open the directory for reading.  If this fails, we're done.
  545.      * If being called from fts_read, set the fts_info field.
  546.      */
  547.     if (!(dirp = opendir(cur->fts_accpath))) {
  548.         if (type == BREAD)
  549.             cur->fts_info = FTS_DNR;
  550.         return(NULL);
  551.     }
  552.  
  553.     /*
  554.      * Nlinks is the number of possible entries of type directory in the
  555.      * directory if we're cheating on stat calls, 0 if we're not doing
  556.      * any stat calls at all, -1 if we're doing stats on everything.
  557.      */
  558.     nlinks =
  559.         ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
  560.         cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
  561.  
  562.     /*
  563.      * If we're going to need to stat anything or we want to descend
  564.      * and stay in the directory, chdir.  If this fails we keep going.
  565.      * We won't be able to stat anything, but we can still return the
  566.      * names themselves.  Note, that since fts_read won't be able to
  567.      * chdir into the directory, it will have to return different path
  568.      * names than before, i.e. "a/b" instead of "b".  Since the node
  569.      * has already been visited in pre-order, have to wait until the
  570.      * post-order visit to return the error.  This is all fairly nasty.
  571.      * If a program needed sorted entries or stat information, they had
  572.      * better be checking FTS_NS on the returned nodes.
  573.      */
  574.     if (nlinks || type == BREAD)
  575. #ifdef _POSIX_SOURCE
  576.         if (CHDIR(sp, cur->fts_accpath)) {
  577. #else
  578.         if (FCHDIR(sp, dirfd(dirp))) {
  579. #endif
  580.             if (type == BREAD)
  581.                 cur->fts_cderr = errno;
  582.             descend = nlinks = 0;
  583.             cderr = 1;
  584.         } else {
  585.             descend = 1;
  586.             cderr = 0;
  587.         }
  588.     else
  589.         descend = 0;
  590.  
  591.         /*
  592.      * Figure out the max file name length that can be stored in the
  593.      * current path -- the inner loop allocates more path as necessary.
  594.      * We really wouldn't have to do the maxlen calculations here, we
  595.      * could do them in fts_read before returning the path, but it's a
  596.      * lot easier here since the length is part of the dirent structure.
  597.      *
  598.      * If not changing directories set a pointer so that we can just
  599.      * append each new name into the path.
  600.      */
  601.     maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
  602.     len = NAPPEND(cur);
  603.     if (ISSET(FTS_NOCHDIR)) {
  604.         cp = sp->fts_path + len;
  605.         *cp++ = '/';
  606.     }
  607.  
  608.     level = cur->fts_level + 1;
  609.  
  610.     /* Read the directory, attaching each entry to the `link' pointer. */
  611.     for (head = NULL, nitems = 0; dp = readdir(dirp);) {
  612.         if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
  613.             continue;
  614.  
  615. #ifdef _POSIX_SOURCE
  616.         if (!(p = fts_alloc(sp, dp->d_name, strlen (dp->d_name))))
  617. #else
  618.         if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)))
  619. #endif
  620.             goto mem1;
  621. #ifdef _POSIX_SOURCE
  622.         if (strlen (dp->d_name) > maxlen) {
  623. #else
  624.         if (dp->d_namlen > maxlen) {
  625. #endif
  626. #ifdef _POSIX_SOURCE
  627.             if (!fts_path(sp, strlen (dp->d_name))) {
  628. #else
  629.             if (!fts_path(sp, (int)dp->d_namlen)) {
  630. #endif
  631.                 /*
  632.                  * No more memory for path or structures.  Save
  633.                  * errno, free up the current structure and the
  634.                  * structures already allocated.
  635.                  */
  636. mem1:                saved_errno = errno;
  637.                 if (p)
  638.                     free(p);
  639.                 fts_lfree(head);
  640.                 (void)closedir(dirp);
  641.                 errno = saved_errno;
  642.                 cur->fts_info = FTS_ERR;
  643.                 SET(FTS_STOP);
  644.                 return(NULL);
  645.             }
  646.             maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
  647.         }
  648.  
  649. #ifdef _POSIX_SOURCE
  650.         p->fts_pathlen = len + strlen (dp->d_name) + 1;
  651. #else
  652.         p->fts_pathlen = len + dp->d_namlen + 1;
  653. #endif
  654.         p->fts_parent = sp->fts_cur;
  655.         p->fts_level = level;
  656.  
  657.         if (nlinks) {
  658.             /* Build a file name for fts_stat to stat. */
  659.             if (ISSET(FTS_NOCHDIR)) {
  660.                 p->fts_accpath = p->fts_path;
  661.                 bcopy(p->fts_name, cp, p->fts_namelen + 1);
  662.             } else
  663.                 p->fts_accpath = p->fts_name;
  664.             p->fts_info = fts_stat(sp, p, 0);
  665.             if (nlinks > 0 && p->fts_info == FTS_D)
  666.                 --nlinks;
  667.         } else if (cderr) {
  668.             p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS;
  669.             p->fts_accpath = cur->fts_accpath;
  670.         } else {
  671.             p->fts_accpath =
  672.                 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
  673.             p->fts_info = FTS_NSOK;
  674.         }
  675.  
  676.         p->fts_link = head;
  677.         head = p;
  678.         ++nitems;
  679.     }
  680.     (void)closedir(dirp);
  681.  
  682.     /*
  683.      * If not changing directories, reset the path back to original
  684.      * state.
  685.      */
  686.     if (ISSET(FTS_NOCHDIR)) {
  687.         if (cp - 1 > sp->fts_path)
  688.             --cp;
  689.         *cp = '\0';
  690.     }
  691.  
  692.     /*
  693.      * If descended after called from fts_children or called from
  694.      * fts_read and didn't find anything, get back.  If can't get
  695.      * back, we're done.
  696.      */
  697.     if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
  698.         cur->fts_info = FTS_ERR;
  699.         SET(FTS_STOP);
  700.         return(NULL);
  701.     }
  702.  
  703.     /* If we didn't find anything, just do the post-order visit */
  704.     if (!nitems) {
  705.         if (type == BREAD)
  706.             cur->fts_info = FTS_DP;
  707.         return(NULL);
  708.     }
  709.  
  710.     /* Sort the entries. */
  711.     if (sp->fts_compar && nitems > 1)
  712.         head = fts_sort(sp, head, nitems);
  713.     return(head);
  714. }
  715.  
  716. static u_short
  717. fts_stat(sp, p, follow)
  718.     FTS *sp;
  719.     register FTSENT *p;
  720.     int follow;
  721. {
  722.     int saved_errno;
  723.  
  724.     /*
  725.      * If doing a logical walk, or application requested FTS_FOLLOW, do
  726.      * a stat(2).  If that fails, check for a non-existent symlink.  If
  727.      * fail, return the errno from the stat call.
  728.      */
  729.     if (ISSET(FTS_LOGICAL) || follow) {
  730.         if (stat(p->fts_accpath, &p->fts_statb)) {
  731.             saved_errno = errno;
  732.             if (!lstat(p->fts_accpath, &p->fts_statb)) {
  733.                 errno = 0;
  734.                 return(FTS_SLNONE);
  735.             } 
  736.             errno = saved_errno;
  737.             bzero(&p->fts_statb, sizeof(struct stat));
  738.             return(FTS_NS);
  739.         }
  740.     } else if (lstat(p->fts_accpath, &p->fts_statb)) {
  741.         bzero(&p->fts_statb, sizeof(struct stat));
  742.         return(FTS_NS);
  743.     }
  744.  
  745.     /*
  746.      * Cycle detection is done as soon as we find a directory.  Detection
  747.      * is by brute force; if the tree gets deep enough or the number of
  748.      * symbolic links to directories high enough something faster might
  749.      * be worthwhile.
  750.      */
  751.     if (S_ISDIR(p->fts_statb.st_mode)) {
  752.         register FTSENT *t;
  753.         register dev_t dev;
  754.         register ino_t ino;
  755.  
  756.         dev = p->fts_statb.st_dev;
  757.         ino = p->fts_statb.st_ino;
  758.         for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL;
  759.             t = t->fts_parent)
  760.             if (ino == t->fts_statb.st_ino &&
  761.                 dev == t->fts_statb.st_dev) {
  762.                 sp->fts_savelink = p->fts_link;
  763.                 p->fts_link = t;
  764.                 return(FTS_DC);
  765.             }
  766.         return(FTS_D);
  767.     }
  768.  
  769. #ifndef _POSIX_SOURCE
  770.         if (S_ISLNK(p->fts_statb.st_mode))
  771.             return(FTS_SL);
  772. #endif
  773.     if (S_ISREG(p->fts_statb.st_mode))
  774.         return(FTS_F);
  775.     return(FTS_DEFAULT);
  776. }
  777.  
  778. #define    R(type, nelem, ptr) \
  779.     (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
  780.  
  781. static FTSENT *
  782. fts_sort(sp, head, nitems)
  783.     FTS *sp;
  784.     FTSENT *head;
  785.     register int nitems;
  786. {
  787.     register FTSENT **ap, *p;
  788.  
  789.     /*
  790.      * Construct an array of pointers to the structures and call qsort(3).
  791.      * Reassemble the array in the order returned by qsort.  If unable to
  792.      * sort for memory reasons, return the directory entries in their
  793.      * current order.  Allocate enough space for the current needs plus
  794.      * 40 so we don't realloc one entry at a time.
  795.      */
  796.     if (nitems > sp->fts_nitems) {
  797.         sp->fts_nitems = nitems + 40;
  798.         if (!(sp->fts_array =
  799.             R(FTSENT *, sp->fts_nitems, sp->fts_array))) {
  800.             sp->fts_nitems = 0;
  801.             return(head);
  802.         }
  803.     }
  804.     for (ap = sp->fts_array, p = head; p; p = p->fts_link)
  805.         *ap++ = p;
  806.     qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
  807.     for (head = *(ap = sp->fts_array); --nitems; ++ap)
  808.         ap[0]->fts_link = ap[1];
  809.     ap[0]->fts_link = NULL;
  810.     return(head);
  811. }
  812.  
  813. static FTSENT *
  814. fts_alloc(sp, name, len)
  815.     FTS *sp;
  816.     char *name;
  817.     register int len;
  818. {
  819.     register FTSENT *p;
  820.  
  821.     /*
  822.      * Variable sized structures; the name is the last element so
  823.      * we allocate enough extra space after the structure to store
  824.      * it.
  825.      */
  826.     if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
  827.         return(NULL);
  828.     bcopy(name, p->fts_name, len + 1);
  829.     p->fts_namelen = len;
  830.     p->fts_path = sp->fts_path;
  831.     p->fts_instr = FTS_NOINSTR;
  832.     p->fts_cderr = 0;
  833.     p->fts_number = 0;
  834.     p->fts_pointer = NULL;
  835.     return(p);
  836. }
  837.  
  838. static void
  839. fts_lfree(head)
  840.     register FTSENT *head;
  841. {
  842.     register FTSENT *p;
  843.  
  844.     /* Free a linked list of structures. */
  845.     while (p = head) {
  846.         head = head->fts_link;
  847.         free(p);
  848.     }
  849. }
  850.  
  851. /*
  852.  * Allow essentially unlimited paths; certain programs (find, rm, ls) need to
  853.  * work on any tree.  Most systems will allow creation of paths much longer
  854.  * than MAXPATHLEN, even though the kernel won't resolve them.  Add an extra
  855.  * 128 bytes to the requested size so that we don't realloc the path 2 bytes
  856.  * at a time.
  857.  */
  858. static char *
  859. fts_path(sp, size)
  860.     FTS *sp;
  861.     int size;
  862. {
  863.     sp->fts_pathlen += size + 128;
  864.     return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path));
  865. }
  866.